🏟️ Maximum Matches Scheduling (Activity Selection)

Visualize the Greedy Algorithm for scheduling maximum non-overlapping cricket matches.

🏏 The Cricket Stadium Challenge

🎯 The Challenge:

Schedule the **maximum number of non-overlapping cricket matches** on a single ground, given a list of matches with start and end times.

📋 Key Constraints:

  • Only one match can be played at a time.
  • A match can start immediately when the previous one finishes.
  • Goal: **Maximize** the count of scheduled matches.

Problem Specifications (Example Input)

The input is structured as: N, followed by (Name, Start Time, End Time) for each match.

6
match1
1
2
match5
3
4
match4
0
6
match3
5
7
match6
8
9
match2
5
9

Expected Output for Example

Selected Activities are: match1 match5 match3 match6

🧠 The Greedy Strategy

Key Idea: Earliest Finish Time

  1. **Sort:** Sort all matches based on their **finish times** in ascending order.
  2. **Select First:** Always select the first match (the one that finishes earliest).
  3. **Iterate:** Look for the next match whose **start time** is greater than or equal to the finish time of the last selected match.
  4. **Greedy Choice:** Always select that next possible match with the earliest finish time.

Time Complexity

O(N log N)

Dominated by the initial $O(N \log N)$ sorting step.

Space Complexity

O(N)

To store the list of matches and the resulting schedule.

🔍 Step-by-Step Selection Demo

Enter data as: name Start End
Ready. Click Start to initialize the matches.

Sorted Match List (by Finish Time)

Click Start to run the greedy selection process.

✅ Selected Schedule

No matches selected yet.

Progress tracker

1. Parse and validate input data.
2. **Sort** matches by their finish times.
3. Select the first match. Set `last_finish_time`.
4. Iterate through remaining matches: check non-overlap condition (`start >= last_finish_time`).
5. If non-overlapping, **select** match, update `last_finish_time`.
6. Repeat until all matches are checked.

🎮 Practice Match Scheduling

Enter matches and press Find Max Schedule

Timeline Visualization (Min-Max Time: N/A)

📊 Analysis & Why Greedy Works

Optimality Proof

Yes

Selecting the match that finishes earliest leaves the most time remaining for subsequent matches.

Alternative

Dynamic Programming

DP could solve it, but is more complex and less efficient than the $O(N \log N)$ greedy approach.

The Greedy Choice Property

  • The problem exhibits **optimal substructure**: The optimal solution to the original problem contains within it an optimal solution to subproblems.
  • The choice of the earliest finishing match is always part of an optimal solution. This choice doesn't depend on future choices but guarantees maximum remaining time.